package com.feng.designpattern.strategy.sortarray;

/**
 * @author Administrator
 * Shell排序：
 * 它是对插入排序的一种改进，是考虑将集合元素按照一定的基数划分成组去排序，让每一组在局部范围内先排成基本有序，最后在进行一次所有元素的插入排序。
	public static int[] shellSort(int[] data) {
		for (int i = data.length / 2; i > 2; i /= 2) {
			for (int j = 0; j < i; j++) {
				insertSort(data, j, i);
			}
		}
		insertSort(data, 0, 1);
		return data;
	}

	private static void insertSort(int[] data, int start, int inc) {
		int temp;
		for (int i = start + inc; i < data.length; i += inc) {
			for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
				temp = data[j];
				data[j] = data[j - inc];
				data[j - inc] = temp;
			}
		}
	}
 */
public class ShellSort extends SortStrategy {
	public void sort(int[] data) {
		// 快速排序法(Quick Sort)
		long begin = System.currentTimeMillis();
		shellSort(data);
		long end = System.currentTimeMillis();
		System.out.println("快速法用时为：" + (end - begin));
		// 打印排序好的结果
		for (int i = 0; i < data.length; i++) {
			System.out.println(data[i]);
		}
	}

	public static int[] shellSort(int[] data) {
		for (int i = data.length / 2; i > 2; i /= 2) {
			for (int j = 0; j < i; j++) {
				insertSort(data, j, i);
			}
		}
		insertSort(data, 0, 1);
		return data;
	}

	private static void insertSort(int[] data, int start, int inc) {
		int temp;
		for (int i = start + inc; i < data.length; i += inc) {
			for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
				temp = data[j];
				data[j] = data[j - inc];
				data[j - inc] = temp;
			}
		}
	}
}
